package sword.T38;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-06-22 20:13:11 星期二
 */

class Solution {
    // 一刷
    /*public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        boolean[] used = new boolean[s.length()];
        StringBuilder sb = new StringBuilder();
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if(i > 0 && chars[i] == chars[i-1]) {
                continue;
            }
            dfs(chars, used, i, sb, ans, true);
        }
        return ans.toArray(new String[0]);
    }

    private void dfs(char[] chars, boolean[] used, int cur, StringBuilder sb, List<String> ans, boolean flag) {
        sb.append(chars[cur]);
        used[cur] = true;
        if(sb.length() == chars.length) {
            ans.add(sb.toString());
            sb.deleteCharAt(sb.length()-1);
            used[cur] = false;
            return;
        }
        for(int i=0; i<chars.length; ++i) {
            if((i > 0 && chars[i-1] == chars[i] && !used[i-1]) || used[i]) {
                continue;
            }
            dfs(chars, used, i, sb, ans, false);
        }
        sb.deleteCharAt(sb.length()-1);
        used[cur] = false;
    }*/

    // 二刷
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        boolean[] used = new boolean[chars.length];
        StringBuilder path = new StringBuilder();
        List<String> result = new ArrayList<>();
        Arrays.sort(chars);
        for (int i=0; i<chars.length; ++i) {
            if (i > 0 && chars[i] == chars[i-1])
                continue;
            dfs(result, path, chars, used, i);
        }

        return result.toArray(new String[result.size()]);
    }

    private void dfs(List<String> result, StringBuilder path, char[] chars, boolean[] used, int cur) {
        path.append(chars[cur]);
        if (path.length() == chars.length) {
            result.add(path.toString());
            path.deleteCharAt(path.length()-1);
            return;
        }
        used[cur] = true;
        for (int i=0; i<chars.length; ++i) {
            if (used[i] || (i > 0 && chars[i-1] == chars[i] && !used[i-1]))
                continue;
            dfs(result, path, chars, used, i);
        }
        used[cur] = false;
        path.deleteCharAt(path.length()-1);
    }
}